/************** ____                          __                ***************
*************  /\  _`\    __                 /\ \                 *************
*************  \ \ \L\ \ /\_\     __     _ __\ \ \/'\      __     *************
*************   \ \  _ <'\/\ \  /'__`\  /\`'__\ \ , <    /'__`\   *************
*************    \ \ \L\ \\ \ \/\ \L\.\_\ \ \/ \ \ \\`\ /\  __/   *************
*************     \ \____/_\ \ \ \__/.\_\\ \_\  \ \_\ \_\ \____\  *************
************* 	   \/___//\ \_\ \/__/\/_/ \/_/   \/_/\/_/\/____/  *************
***************            \ \____/                               *************
***************             \/___/                               *************/
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
#include "Node2.h"

using namespace std;
class McC{
private:
	string str, searchString; 
	Node * root;
	vector<int> * resultvec;
	
	Node * head;
	Node * nextHead;
	Node * parent;
	int tail;
	int headOldLength;
	int i;
	string x;

	Node* parent;
	Node* child;
	int nextTailL;
	int edgeMatch;

public:
	char getCharAt(int i){
		return str[i];
	}
	Node * getRoot(){
		return root;		
	}

	void printNode(Node * n){
		cout <<   "(" << n->getEdge(str) << ","<< ")";

		if(n->child==NULL){
			cout << ", suffix" << n->suffix;
		}
		else{
			cout << ".blade " << n->lowLeaf << "-" << n->highLeaf ;
		}
		//cout << "(d:" << n->depth << "))";
	}

	void printTree(int i, Node * n){
		if(n==NULL) return;	
		for(int a=0;a<i;a++) cout << "-";
		printNode(n);
		cout  << endl;
		printTree(i+1,n->child);
		printTree(i,n->sibling);
	}



	void printStatus(){
		cout << "status: ";
		printNode(parent);
		cout << ", ";
		printNode(child);
		cout << ", " << edgeMatch << endl;
	}

	McC(string s){
		str= (s+"$");

		initializeSuffixTree();
		for(i = 1; i < str.length()-1; i++){
			nextTailL = i;

			if(head == root){
				//simple case. We slowscan for head(i+1) from root.
				parent = root;
				nextHead = slowScan(root, i, str.length());

				if(edgeMatch == 0){
					//if edgeMatch ==0, then head(i+1) is on a Node
					nextHead = child;
					addTerminal(child, nextTailL, i);
				}
				else{
					//else, we start by adding an inner, then adding the next terminal
					nextHead = addInner();
					addTerminal(nextHead, nextTailL, i);
				}
				

			}else{
				// w is either a Node, or a string. That is difficult to write,
				// so w is implicitely written in parent, child and edgeMatch


				//if parent != root, we have a good suffixPointer to help us find w
				if(parent != root){
					parent = parent->suffixNode;

					fastScan(parent->suffixNode, head->l, head->r);
					nextTailL = i + headOldLength-1;
				}else{
					//else, we just try to find w from the root
					parent = root;
					fastScan(root, head->l+1, head->r);
				}

				Node* w;
				if(edgeMatch == 0){
					//we found w on a Node. We slowscan for head(i+1) from there
					w = child;

					slowScan(child, tail, str.length());

					if(edgeMatch == 0){
						//head(i+1) is already a Node
						nextHead = child;
					}else{
						//head(i+1) is on an edge. We add next Inner Node
						nextHead = addInner();
					}
				}else{
					//if w is on an edge we add next inner Node, and set head(i+1) = w
					w = addInner();
					nextHead = w;
				}

				head->suffixNode = w;

				//now that we found and added head(i+1), we just need to add the next Terminal
				
				addTerminal(nextHead, nextTailL, i);
				
				
			}


			//now we have found head(i+1), and added the next terminal.
			headOldLength = nextTailL - i; 
			head = nextHead;
			tail = nextTailL;
			parent = parent;

		}

		appendEmptyNode();
		cout << "-------------done!----------------" << endl;
		result("Walrus");
	}

	void initializeSuffixTree(){
		root = new Node(0, 0,0);
		root->suffixNode = root;

		root->child = new Node(0,str.length(),0);

		head = root;
		tail = 0;
		parent = root;
	}

	void appendEmptyNode(){
		Node* final = new Node(str.length()-1, str.length(), str.length()-1);
		if(root->child == NULL){
			root->child = final;
		}else{
			Node* sib = root->child;
			while(sib->sibling != NULL){
				sib = sib->sibling;
			}
			sib->sibling = final;
		}

	}

	Node* findEdge(char a, Node* n){

		Node* current = n->child;

		while(true){



			if(current == NULL){
				return NULL;
			}
			string edge = current->getEdge(str);
			if(edge[0]==a){
				return current;
			}
			else current=current->sibling;
		}
	}

	int walkedge(Node * n, int l, int r){
		string edge= n->getEdge(str);


		int count=0;
		while(true){
			if(l+count>=r) return count;
			else if(edge.length()==count) return count;
			else if(edge[count]!=str[l+count]) return count;
			else count++;
		}
	}

	int walkedge2(Node * n, int l, int r){
		string edge= n->getEdge(str);


		int count=0;
		while(true){
			if(l+count>=r) return count;
			else if(edge.length()==count) return count;
			else if(edge[count]!=searchString[l+count]) return count;
			else count++;
		}
	}

	Node * addTerminal(Node* parent, int l, int s){
		Node* nextTerminal = new Node(l, str.length() , s);
		
		if(parent->child == NULL){
			parent->child = nextTerminal;
		}
		else{
			Node* sib = parent->child;
			while(sib->sibling != NULL){
				sib = sib->sibling;
			}
			sib->sibling = nextTerminal;
		}
		tail = l;
		return nextTerminal;
	}

	//add an inner Node between "parent" and "child"
	Node* addInner(){
		Node* nextInner = new Node(child->l, child->l + edgeMatch, -1);
		if(parent->child == child){
			parent->child = nextInner;
		}
		else{
			Node* sib = parent->child;
			while(sib->sibling != child){
				sib = sib->sibling;
			}
			sib->sibling = nextInner;
		}
		nextInner->child = child;
		nextInner->sibling = child->sibling;
		child->l = child->l + edgeMatch;
		child->sibling = NULL;
		return nextInner;
	}

	Node * slowScan(Node* n, int l, int r){
		Node * temp= findEdge(str[l],n);

		
		//if temp==NULL, n represents the longest match, head(i+1). 
		if(temp==NULL){
			child = n;
			edgeMatch = 0;
			return n;
		}

		//else, we see how far we can match
		edgeMatch= walkedge(temp,l,r);

		//if we can match the full edge, we call recursively
		if(edgeMatch == temp->getEdge(str).length()){
			parent = n;
			nextTailL += edgeMatch;
			return slowScan(temp,l+edgeMatch,r);	
			
		} //else, head(i+1) is on temp's edge. We can return.
		else{
			parent = n;
			child = temp;
			nextTailL = nextTailL+edgeMatch;       
			return n;
		}
	}




	Node * fastScan(Node* n, int l, int r){

		// if l == r, then we have found w
		if(l == r){
			child = n;
			edgeMatch = 0;
			return n;

		}else{
			Node* temp = findEdge(str[l], n);
			int length = r-l;
			int edgeLength = temp->r - temp->l;
			
			//if the searchstring is longer than the edge we are looking at, we call recursively
			if(length >= edgeLength){
				parent = n;
				parent = n;
				nextTailL += edgeLength;
				return fastScan(temp, l+edgeLength, r);
			}else{
				//if w is on an edge, we can return
				parent = n;
				child = temp;
				edgeMatch = length;
				nextTailL +=length; 
				return n;
			}
		}

	}

	Node * resultSlowscan(Node * n, int l, int r){
		//printNode(n);
		if(l==r) return n;
		else{
			Node * temp= findEdge(searchString[l],n);
			if(temp==NULL) return NULL;
			else{
				int match= walkedge2(temp,l,r);
				int length= temp->r-temp->l;
				if(match>=length) return  resultSlowscan(temp,l+match,r);
				else return temp;
			}
		}

	}

	void countChildren(Node * n){
		if(n==NULL) return;
		if(n->child==NULL) resultvec->push_back(n->suffix);
		countChildren(n->child);
		countChildren(n->sibling);
	}

	vector<int> * result(string s){
		searchString=s;	
		resultvec= new vector<int>();
		Node * searchNode= resultSlowscan(root,0,s.length());
		if(searchNode != NULL){
			printNode(searchNode);
			cout << endl;
		}else{
			cout << "is null" << endl;
		}
		//cout << endl << endl;
		if(searchNode==NULL) return resultvec;
		if(searchNode->child==NULL) resultvec->push_back(searchNode->suffix);
		else countChildren(searchNode->child);
		return resultvec;
	}

};
